package com.example;

import java.util.Stack;

/**
 * @Author loubobooo
 * @Description #75. 颜色分类
 * @Date 2022/3/22
 */
public class SortColors {

    /**
     * 给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
     * 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
     * 必须在不使用库的sort函数的情况下解决这个问题。
     * 冒泡排序
     *
     * @param nums
     */
    public void sortColors(int[] nums) {
        // 数组分成三部分left、pivot、right，使left<=pivot，right>pivot
        //递归处理left
        //递归处理right
        //合并三者结果
        quickSort(nums, 0, nums.length - 1);
    }

    private void quickSort(int[] nums, int left, int right) {
        if (left > right) {
            return;
        }
        // 基准量
        int privot = nums[left];
        int l = left;
        int r = right;
        while (l < r) {
            // 迭代从右往左找，直到找到小于基准量的索引
            while (l < r && nums[r] >= privot) {
                r--;
            }
            // 迭代从左往右找，直到找到大于基准量的索引
            while (l < r && nums[l] <= privot) {
                l++;
            }
            // swap 两者交换值
            int temp = nums[l];
            nums[l] = nums[r];
            nums[r] = temp;
        }
        // 在找到l=r终止之后，交换l与privot基准量值
        nums[left] = nums[l];
        nums[l] = privot;
        // 递归找左边
        quickSort(nums, left, l - 1);
        // 递归找右边
        quickSort(nums, r + 1, right);
    }

    private void quickSortNR(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        Stack<Integer> stack = new Stack<>();
        stack.push(left);
        stack.push(right);
        //其实就是用栈保存每一个待排序子串的首尾元素下标，下一次while循环时取出这个范围，对这段子序列进行partition操作
        while (!stack.empty()) {
            int q = stack.pop();
            int p = stack.pop();
            int mid = partition(nums, p, q);
            if (p < mid - 1) {
                stack.push(p);
                stack.push(mid - 1);
            }
            if (mid + 1 < q) {
                stack.push(mid + 1);
                stack.push(q);
            }
        }
    }

    private int partition(int[] nums, int left, int right) {
        if (left > right) {
            return -1;
        }
        // 基准量
        int privot = nums[left];
        int l = left;
        int r = right;
        while (l != r) {
            // 迭代从右往左找，直到找到小于基准量的索引
            while (l < r && nums[r] >= privot) {
                r--;
            }
            // 迭代从左往右找，直到找到大于基准量的索引
            while (l < r && nums[l] <= privot) {
                l++;
            }
            // swap 两者交换值
            int temp = nums[l];
            nums[l] = nums[r];
            nums[r] = temp;
        }
        // 在找到l=r终止之后，交换l与privot基准量值
        nums[left] = nums[l];
        nums[l] = privot;
        return l;
    }

    public static void main(String[] args) {
        SortColors sortColors = new SortColors();
        int[] nums = new int[]{4, 3, 9, 3, 7, 9};
        sortColors.quickSortNR(nums);
    }


}
